#ifndef RB_TREE_H
#define RB_TREE_H

namespace RBT {
    
    enum Color{red,black};

    template<class T>
    class RBNode{
        public:
        T val;
        Color color;
        RBNode<T>*left;
        RBNode<T>*right;
        RBNode<T>*father;

        RBNode(T val,Color color,RBNode<T>*father){
            this->val=val;
            this->color=color;
            this->right=nullptr;
            this->left=nullptr;
            this->father=father;
        }
        RBNode(RBNode<T>&node){
            this->val=node.val;
            this->color=node.color;
            this->left=node.left;
            this->right=node.right;
            this->father=node.father;
        }

        void replace(RBNode<T>*node){
            this->val=node->val;
            this->left=node->left;
            this->right=node->right;
            this->father=node->father;
        }

        ~RBNode(){}
        static void left_rotate(RBNode<T>*N);
        static void right_rotate(RBNode<T>*N);
    };

    template<class T>
    class RBTree{
        RBNode<T>*root;
        public:
        RBTree(){
            root=nullptr;
        }
        RBTree(T val){
            root=new RBNode<T>(val,black);
        }
        ~RBTree(){
            delete root;
            root=nullptr;
        }
        void rb_insert(T val);
        RBNode<T>* rb_search(T val);
        void rb_delete(T val);
        private:
        static void insert_recolor(RBNode<T>*node);
        static void delete_recolor(RBNode<T>*node);
    };
}

#endif